package AlgorithmStudy.study.study01;


import java.util.Arrays;

/**
 * 堆排序
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] arr = new int[]{2,5,6,7,3,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }



    public static void sort(int[] arr){
        int len = arr.length;
        // 构建堆  - 大顶堆(因为后续需要将元素与堆尾交换 剩余数据继续构建大顶堆)
        for (int i = len/2-1; i>=0; i--){
            buildMaxHeap(arr,i,len);
        }

        for (int i=len-1; i>0; i--){
            // 交换堆顶 尾 元素
            swap(arr, 0, i);
            len--;
            // 固定堆尾 剩余元素继续构建堆
            buildMaxHeap(arr, 0, len);
        }

    }



    private static void buildMaxHeap(int[] arr, int i, int len) {
        int left = 2*i+1;
        int right = 2*i+2;
        int tempIndex = i;

        if (left<len && arr[left]>arr[tempIndex]){
             tempIndex = left;
        }
        if(right<len && arr[right]>arr[tempIndex]){
            tempIndex = right;
        }

        if (tempIndex!=i){
            swap(arr, tempIndex, i);
            buildMaxHeap(arr, tempIndex, len);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
